package varvelworld.algorithm.DuplicationFinding;

import java.util.ArrayList;
import java.util.List;

public class BalanceTree implements IDuplicationFinding {

    @Override
    public List<Long> execute(long[] a) {
        List<Long> result = new ArrayList<Long>();
        Node root = new Node(a[0], 1);
        for(int i = 1; i < a.length; i++){
            if(insert(root, a[i], result)){
                root = balance(root);//平衡节点
            }
        }
        return result;
    }
    
    static boolean insert(Node node, long d, List<Long> result){
        if(d == node.v){
            node.s++;
            if(node.s == 2){
                result.add(node.v);
            }
            return false;
        }
        else if(d < node.v){
            if(node.left == null){
                node.left = new Node(d, 1);
                node.lh++;
                return node.lh > node.rh;
            }
            else{
                boolean istaller = insert(node.left, d, result);
                if(istaller){
                    Node next = balance(node.left);
                    if(node.left == next){
                        node.lh++;
                        return node.lh > node.rh;
                    }
                    else{
                        node.left = next;
                        return false;
                    }
                }
                return false;
            }
        }
        else{
            if(node.right == null){
                node.right = new Node(d, 1);
                node.rh++;
                return node.rh > node.lh;
            }
            else{
               boolean istaller = insert(node.right, d, result);
               if(istaller) {
                   Node next = balance(node.right);
                   if(node.right == next){
                       node.rh++;
                       return node.rh > node.lh;
                   }
                   else{
                       node.right = next;
                       return false;
                   }
               }
               return false;
            }
        }
    }

    static Node balance(Node node){
        Node root = node;
        int a = node.lh - node.rh;//平衡因子
        if(a > 1){//a == 2
            a = node.left.lh - node.left.rh;
            if(a > 0){//a == 1
                //LL型
                root = rightRotate(node);
            }
            else if(a < 0){//a == -1
                //LR型
                root = leftRightRotate(node);
            }
        }
        else if(a < -1){//a == -2
            a = node.right.lh - node.right.rh;
            if(a < 0){//a == -1
                //RR型
                root = leftRotate(node);
            }
            else if(a > 0){//a == 1
                //RL型
                root = rightLeftRotate(node);
            }
        }
        return root;
    }
    
    static Node leftRotate(Node node){
        Node a = node;
        Node b = a.right;
        a.right = b.left;
        b.left = a;
        a.rh = a.lh;
        b.lh = b.rh;
        return b;
    }
    
    static Node rightRotate(Node node){
        Node a = node;
        Node b = a.left;
        a.left = b.right;
        b.right = a;
        a.lh = a.rh;
        b.rh = b.lh;
        return b;
    }
    
    static Node leftRightRotate(Node node){
        Node a = node;
        Node b = a.left;
        Node c = b.right;
        int h = a.rh;
        b.right = c.left;
        a.left = c.right;
        c.left = b;
        c.right = a;
        a.lh = c.rh;
        b.rh = c.lh;
        c.rh = c.lh = h + 1;
        return c;
    }
    
    static Node rightLeftRotate(Node node){
        Node a = node;
        Node b = a.right;
        Node c = b.left;
        int h = a.lh;
        a.right = c.left;
        b.left = c.right;
        c.left = a;
        c.right = b;
        a.rh = c.lh;
        b.lh = c.rh;
        c.rh = c.lh = h + 1;
        return c;
    }
    
    static class Node{
        long v;
        int s;
        Node left, right;
        int lh, rh;
        public Node(long v, int s){
            super();
            this.v = v;
            this.s = s;
        }
        
    }
}
